From digital genetics to knowledge discovery Perspectives in genetic network understanding.

Combining sequence and itemset mining to discover named entities in biomedical texts a new type of pattern.

Parameter Tuning for Differential Mining of String Patterns.
Constraint-based mining has been proven to be extremely useful for supporting actionable pattern discovery. However, useful conjunctions of constraints that support domain driven mining tasks generally need to set several parameter values and how to tune these parameters remains fairly open. We study this problem for substring pattern discovery, when using a conjunction of maximal frequency, minimal frequency and size constraints. We propose a method, based on pattern space sampling, to estimate the number of patterns that satisfy such conjunctions. This permits the user to probe the parameter space in many points, and then to choose some initial promising parameter settings. Our empirical validation confirms that we efficiently obtain good approximations of the number of patterns that will be extracted. 1.
Automatic generation of CHR constraint solvers.
In this paper, we present a framework for automatic generation of CHR solvers given the logical speci  cation of the constraints. This approach takes advantage of the power of tabled resolution for constraint logic programming, in order to check the validity of the rules. Compared to previous work (Apt &amp; Monfroy, 1999; Ringeissen &amp; Monfroy, 2000; Abdennadher &amp; Rigotti, 2000; Abdennadher &amp; Rigotti, 2001a), where dierent methods for automatic generation of constraint solvers have been proposed, our approach enables the generation of more expressive rules (even recursive and splitting rules) that can be used directly as CHR solvers.
A Survey on Condensed Representations for Frequent Sets.
Abstract. Solving inductive queries which have to return complete collections of patterns satisfying a given predicate has been studied extensively the last few years. The specific problem of frequent set mining from potentially huge boolean matrices has given rise to tens of efficient solvers. Frequent sets are indeed useful for many data mining tasks, including the popular association rule mining task but also feature construction, association-based classification, clustering, etc. The research in this area has been boosted by the fascinating concept of condensed representations w.r.t. frequency queries. Such representations can be used to support the discovery of every frequent set and its support without looking back at the data. Interestingly, the size of condensed representations can be several orders of magnitude smaller than the size of frequent set collections. Most of the proposals concern exact representations while it is also possible to consider approximated ones, i.e., to trade computational complexity with a bounded approximation on the computed support values. This paper surveys the core concepts used in the recent works on condensed representation for frequent sets. 1
Integrity Constraints over Association Rules.

Constraint%2DBased Mining of Episode Rules and Optimal Window Sizes.
Abstract. Episode rules are patterns that can be extracted from a large event sequence, to suggest to experts possible dependencies among occurrences of event types. The corresponding mining approaches have been designed to find rules under a temporal constraint that specifies the maximum elapsed time between the first and the last event of the occurrences of the patterns (i.e., a window size constraint). In some applications the appropriate window size is not known, and furthermore, this size is not the same for different rules. To cope with this class of applications, it has been recently proposed in [2] to specifying the maximal elapsed time between two events (i.e., a maximum gap constraint) instead of a window size constraint. Unfortunately, we show that the algorithm proposed to handle the maximum gap constraint is not complete. In this paper we present a sound and complete algorithm to mine episode rules under the maximum gap constraint, and propose to find, for each rule, the window size corresponding to a local maximum of confidence. We show that the extraction can be efficiently performed in practice on real and synthetic datasets. Finally the experiments show that the notion of local maximum of confidence is significant in practice, since no local maximum are found in random datasets, while they can be found in real ones. 1
Automatic generation of rule%2Dbased constraint solvers over finite domains.
A general approach to implement propagation and... In this paper, we propose a method for generating propagation and simplification rules for constraints over finite domains defined extensionally by e.g. a truth table or their tuples. The generation of rules is performed in two steps. First, propagation rules are generated. Propagation rules do not rewrite constraints but add new ones. Thus, the constraint store may contain superuous constraints. Removing these constraints not only allows saving of space but also decreases the cost of constraint solving. Constraints can be removed using simplification rules. Thus, in a second step some propagation rules are transformed into simplification rules. Furthermore, we show that...
Automatic Generation of CHR Constraint Solvers
In this paper, we present a framework for automatic generation of CHR solvers given the logical speci  cation of the constraints. This approach takes advantage of the power of tabled resolution for constraint logic programming, in order to check the validity of the rules. Compared to previous work (Apt &amp; Monfroy, 1999; Ringeissen &amp; Monfroy, 2000; Abdennadher &amp; Rigotti, 2000; Abdennadher &amp; Rigotti, 2001a), where dierent methods for automatic generation of constraint solvers have been proposed, our approach enables the generation of more expressive rules (even recursive and splitting rules) that can be used directly as CHR solvers.
Extraction de motifs s%E9quentiels fr%E9quents sous contraintes dans des donn%E9es contenant des r%E9p%E9titions cons%E9cutives.

GO%2DSPADE Mining Sequential Patterns over Datasets with Consecutive Repetitions.
Abstract. Databases of sequences can contain consecutive repetitions of items. This is the case in particular when some items represent discretized quantitative values. We show that on such databases, a typical algorithm like the SPADE algorithm tends to loose its efficiency. SPADE is based on the used of lists containing the localization of the occurrences of a pattern in the sequences and these lists are not appropriated in the case of data with repetitions. We introduce the concept of generalized occurrences and the corresponding primitive operators to manipulate them. We present an algorithm called GO-SPADE that extends SPADE to incorporate generalized occurrences. Finally we present experiments showing that GO-SPADE can handle sequences containing consecutive repetitions at nearly no extra cost.
Constraint%2DBased Mining of Sequential Patterns over Datasets with Consecutive Repetitions.
Abstract. Constraint-based mining of sequential patterns is an active research area motivated by many application domains. In practice, the real sequence datasets can present consecutive repetitions of symbols (e.g., DNA sequences, discretized stock market data) that can lead to a very important consumption of resources during the extraction of patterns that can turn even efficient algorithms to become unusable. We propose a constraint-based mining algorithm using an approach that enables to compact these consecutive repetitions, reducing drastically the amount of data to process and speeding-up the extraction time. The technique introduced in this paper allows to retain the advantages of existing state-of-the-art algorithms based on the notion of occurrence lists, while permitting to extend their application fields to datasets containing consecutive repetitions. We analyze the benefits obtained using synthetic datasets, and show that the approach is of practical interest on real datasets.
Free%2DSets A Condensed Representation of Boolean Data for the Approximation of Frequency Queries.
Abstract. Given a large collection of transactions containing items, a basic common data mining problem is to extract the so-called frequent itemsets (i.e., sets of items appearing in at least a given number of transactions). In this paper, we propose a structure called free-sets, from which we can approximate any itemset support (i.e., the number of transactions containing the itemset) and we formalize this notion in the framework of ɛ-adequate representations (H. Mannila and H. Toivonen, 1996. In Proc. of the Second International Conference on Knowledge Discovery and Data Mining (KDD’96), pp. 189–194). We show that frequent free-sets can be efficiently extracted using pruning strategies developed for frequent itemset discovery, and that they can be used to approximate the support of any frequent itemset. Experiments on real dense data sets show a significant reduction of the size of the output when compared with standard frequent itemset extraction. Furthermore, the experiments show that the extraction of frequent free-sets is still possible when the extraction of frequent itemsets becomes intractable, and that the supports of the frequent free-sets can be used to approximate very closely the supports of the frequent itemsets. Finally, we consider the effect of this approximation on association rules (a popular kind of patterns that can be derived from frequent itemsets) and show that the corresponding errors remain very low in practice.
Free%2DSets A Condensed Representation of Boolean Data for the Approximation of Frequency Queries.
Abstract. Given a large collection of transactions containing items, a basic common data mining problem is to extract the so-called frequent itemsets (i.e., sets of items appearing in at least a given number of transactions). In this paper, we propose a structure called free-sets, from which we can approximate any itemset support (i.e., the number of transactions containing the itemset) and we formalize this notion in the framework of ɛ-adequate representations (H. Mannila and H. Toivonen, 1996. In Proc. of the Second International Conference on Knowledge Discovery and Data Mining (KDD’96), pp. 189–194). We show that frequent free-sets can be efficiently extracted using pruning strategies developed for frequent itemset discovery, and that they can be used to approximate the support of any frequent itemset. Experiments on real dense data sets show a significant reduction of the size of the output when compared with standard frequent itemset extraction. Furthermore, the experiments show that the extraction of frequent free-sets is still possible when the extraction of frequent itemsets becomes intractable, and that the supports of the frequent free-sets can be used to approximate very closely the supports of the frequent itemsets. Finally, we consider the effect of this approximation on association rules (a popular kind of patterns that can be derived from frequent itemsets) and show that the corresponding errors remain very low in practice.
DBC a condensed representation of frequent patterns for efficient mining.
Given a large set of data, a common data mining problem is to extract the frequent patterns occurring in this set. The idea presented in this paper is to extract a condensed representation of the frequent patterns called disjunction-bordered condensation (DBC), instead of extracting the whole frequent pattern collection. We show that this condensed representation can be used to regenerate all frequent patterns and their exact frequencies. Moreover, this regeneration can be performed without any access to the original data. Practical experiments show that the DBC can be extracted very efficiently even in difficult cases and that this extraction and the regeneration of the frequent patterns is much more efficient than the direct extraction of the frequent patterns themselves. We compared the DBC with another representation of frequent patterns previously investigated in the literature called frequent closed sets. In nearly all experiments we have run, the DBC have been extracted much more efficiently than frequent closed sets. In the other cases, the extraction times are very close. Key words: data mining, frequent patterns, condensed representations 1
Association Maps as Integrity Constraints in Inductive Databases.

Constraint Solver Synthesis Using Tabled Resolution for Constraint Logic Programming.
The goal of automated program synthesis is to bridge the  gap between what is easy for people to describe and what is possible  to execute on a computer. In this paper, we present a framework for  synthesis of rule-based solvers for constraints given their logical specification. This approach takes advantage of the power of tabled resolution  for constraint logic programming, in order to check the validity of the  rules. Compared to previous work [8, 19, 2, 5, 3], where different methods  for automatic generation of constraint solvers have been proposed, our  approach enables the generation of more expressive rules (even recursive  and splitting rules).
Automatic Generation of Rule%2DBased Solvers for Intentionally Defined Constraints.
A general approach to implement propagation... In this paper, we present a method for generating rule-based solvers for constraint predicates de ned by means of a constraint logic program, even when the constraint domain is infinite
Query%2DDriven Knowledge Discovery via OLAP manipulations.

Towards Inductive Constraint Solving.
A difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation and simplification algorithm. In previous work, different methods for automatic generation of propagation rules [5,17,3] and simplification rules [4] for constraints defined over finite domains have been proposed. In this paper, we present a method for generating rule-based solvers for constraint predicates defined by means of a constraint logic program, even when the constraint domain is infinite. This approach can be seen as a concrete step towards Inductive Constraint Solving.
Generation of Propagation Rules for Intentionally Defined Constraints.

A condensed representation to find frequent patterns.
Given a large set of data, a common data mining problem is  to extract the frequent patterns occurring in this set. The idea presented  in this paper is to extract a condensed representation of the frequent  patterns called disjunction-free sets, instead of extracting the whole frequent  pattern collection. We show that this condensed representation can  be used to regenerate all frequent patterns and their exact frequencies.
Automatic Generation of Propagation Rules for Finite Domains.
A general approach to specify the propagation and simplification process of constraints consists of applying rules over these constraints. In
Using Confluence to Generate Rule%2DBased Constraint Solvers.
A general approach to implement propagation and simplification of constraints consists of applying rules over these constraints. Recently, several proposals have been made to solve finite constraint satisfaction problems by means of automatically generated propagation rules [4, 9, 3]. Since propagation rules do not rewrite constraints but add new ones, the constraint store may contain superfluous constraints. Removing these constraints not only allows saving of space but also decreases the cost of constraint solving. Constraints can be removed using simplification rules. In this paper, we present a method to transform propagation rules into simplification rules using the concept of confluence. The generated rules are implemented in the language Constraint Handling Rules (CHR). An example taken from the field of digital circuit design shows that our approach is of practical use.
Automatic Generation of Propagation Rules for Finite Domains.
A general approach to specify the propagation and simplification process of constraints consists of applying rules over these constraints. In
Query Driven Knowledge Discovery in Multidimensional Data.
We study KDD (Knowledge Discovery in Databases) processes on multidimensional data from a query point of view. Focusing on association rule mining, we consider typical queries to cope with the pre-processing of multidimensional data and the post-processing of the discovered patterns as well. We use a model and a rule-based language stemming from the OLAP multidimensional representation, and demonstrate that such a language ts well for writing KDD queries on multidimensional data. Using an homogeneous data model and our language for expressing queries at every phase of the process appears as a valuable step towards a better understanding of interactivity during the whole process.  1 Introduction  Discovering knowledge from data appears as a complex iterative and interactive process containing many steps: understanding the data, preparing the data set (also called pre-processing), discovering potentially interesting patterns (mining phase), post-processing of discovered patterns and na...
Representing and Reasoning on Conceptual Queries Over Image Databases.
The problem of content management of multimedia data types (e.g., image, video, graphics) is becoming increasingly important with the development of advanced multimedia applications. Traditional database management systems are inadequate for the handling of such data types. They require new techniques for query formulation, retrieval, evaluation, and navigation. In this paper we develop a knowledge-based framework for modeling and retrieving image data by content. To represent the various aspects of an image object&#039;s characteristics, we propose a model which consists of three layers:  (1) Feature and Content Layer, intended to contain image visual features such as contours, shapes, etc.; (2) Object Layer, which provides the (conceptual) content dimension of images; and (3) Schema Layer, which contains the structured abstractions of images, i.e., a general schema about the classes of objects represented in the object layer. We propose two abstract languages on the basis of description l...
Spreadsheet Generation from Rule%2DBased Specifications.
Experimental studies have pointed out that operational spreadsheets contain a lot of errors. In this paper, we propose to use a multidimensional rule-based data manipulation language to specify spreadsheets. This language allows formal declarative de nition of spreadsheet tabular data treatments. The main contribution of this paper is to show that from textual rule-based speci cations, we can generate the corresponding spreadsheet. This generation of a spreadsheet from its logical de nition is a promising way to reduce encoding errors. The technique presented has been implemented in a crude running prototype. 1
Rule%2Dbased restructuring and summarizing in multidimensional data%2Dbases.

A Rule%2DBased CQL for 2%2DDimensional Tables.
. We describe the core of a rule-based CQL, devoted to the manipulation of 2-dimensional tabular databases. The rules provide a simple and declarative way to restructure and query tables, and the constraints allow to define cell contents by formulas over concrete domains. We define a model-theoretic semantics and develop an equivalent fixpoint theory that leads to a naive evaluation procedure. 1 Introduction  Tables are a widely used representation of data. Spreadsheet programs and their tabular data models have become a very popular tool for data presentation and analysis. From a database point of view, the multidimensional tabular representations of data and their manipulations used in On-Line Analytical Processing (OLAP) [6,7] are one of the new challenging technologies. Because of this growing interest, the theoretical foundations of tabular models and their associated languages appear as a motivating field of research. Algebras have recently been designed [8,4], however to our kno...
Extending Datalog for Ordered Multidimensional Databases.
This paper presents a rule-based language that supports multi-dimensional tables. It provides a simple and declarative way to express every query computable in polynomial time on ordered tables. We define its model-theoretic semantics and develop an equivalent fixpoint theory that is a basis for the reuse of standard optimization techniques.
A Rule%2DBased Data Manipulation Language for OLAP Systems.

Abduction et d%E9duction de structures d%27objets une int%E9gration multiparadigmes.

R%E9solution et Classification pour l%27Optimisation S%E9mantique de Requ%EAtes dans les BDOO D%E9ductives.

Une approche multi%2Dparadigmes our le test d%27applications BDOO.

F%2DLogic Programming and Terminological Constraints.

Vers une typologie des s%E9mantiques op%E9rationnelles pour les extensions de Prolog vers les objets.

